package com;

import java.util.Iterator;
import java.util.Random;
import java.util.Set;

import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;

public class TSPairwiseEx {
	
	/*This method uses the pairwise exchange algorithm to solve TS.*/
	
	//Define the graph that will hold the TS tour.
	static SimpleWeightedGraph<Node, DefaultWeightedEdge> tour;
	
	//Define the variable that will hold the answer.
	static double min_dist;
	
	static double compute(SimpleWeightedGraph<Node, DefaultWeightedEdge> graph) {	
		
		//Generate a random TS tour.
		createTour(graph);
		
		//If the graph has less than 4 nodes, then just return as no improvements can be made.
		if (tour.vertexSet().size() < 4) {return min_dist;}
		
		//Create a new random number generator.
		Random generator = new Random();
		
		//Get the size of the set of nodes of the tour.
		int size = tour.vertexSet().size();
		
		//Define the number of iterations the algorithm will carry out. I chose 10x the size of every possible combination of edges. 
		//('size' being odd is not a problem, as integer division returns the whole number part of the answer only)
		int iterNum = ((size-1) - 1) * ((size-1) / 2) * 10;
		
		//Carry out the pairwise exchange till the max number of iterations is reached.
		while (iterNum > 0) {
				//Decrement iteration total by one.
				iterNum -= 1;
				
				//Get a set of all the nodes of 'tour' and convert it into an array. By adding a parameter of type 
				//'node array', it ensures we get an array of type 'node' as opposed to type 'object'.
				Set<Node> vertexSet = tour.vertexSet();
				Node[] nodeArray = vertexSet.toArray(new Node[0]);
				
				//Pick two random nodes.
				Node node1 = nodeArray[generator.nextInt(size)];
				Node node2 = nodeArray[generator.nextInt(size)];
				
				//If they are the same node, then skip the current iteration and carry on.
				if (node1.equals(node2)) {continue;}
				
				//If both edges point to the same node, then skip.
				if (tour.containsEdge(node1, node2)) {continue;}
				
				//Initialise the four affected nodes.
				Node no1ne1 = null;
				Node no1ne2 = null;
				Node no2ne1 = null;
				Node no2ne2 = null;
				
				//A variable that holds the sum of the old weights of the 4 affected edges.
				double sumOf4Edges = 0.0;
				
				//Get the neighbours of node1 and add old weights
				Set<DefaultWeightedEdge> edgesOf1 = tour.edgesOf(node1);
				Iterator<DefaultWeightedEdge> iterE = edgesOf1.iterator();
				while (iterE.hasNext()) {
										//get a random edge connected to the vertex.
										DefaultWeightedEdge edge = iterE.next();
										//find the target vertex of the edge.
										Node node = tour.getEdgeSource(edge);
										Node targetNode;
										if (node.equals(node1)) {targetNode = tour.getEdgeTarget(edge);}
										else {targetNode = node;}
										if (no1ne1==null) {no1ne1 = targetNode;}
										else {no1ne2 = targetNode;}
										sumOf4Edges += tour.getEdgeWeight(edge);} 
										
				//Get the neighbours of node2 and add old weights
				Set<DefaultWeightedEdge> edgesOf2 = tour.edgesOf(node2);
				Iterator<DefaultWeightedEdge> iterE2 = edgesOf2.iterator();
				while (iterE2.hasNext()) {
										//get a random edge connected to the vertex.
										DefaultWeightedEdge edge = iterE2.next();
										//find the target vertex of the edge.
										Node node = tour.getEdgeSource(edge);
										Node targetNode;
										if (node.equals(node2)) {targetNode = tour.getEdgeTarget(edge);}
										else {targetNode = node;}
										if (no2ne1==null) {no2ne1 = targetNode;}
										else {no2ne2 = targetNode;}
										sumOf4Edges += tour.getEdgeWeight(edge);}
												
				//Work out new potential total weight
				double newWeight = 0.0;
				newWeight += graph.getEdgeWeight(graph.getEdge(node2, no1ne1));
				newWeight += graph.getEdgeWeight(graph.getEdge(node2, no1ne2));
				newWeight += graph.getEdgeWeight(graph.getEdge(node1, no2ne1));
				newWeight += graph.getEdgeWeight(graph.getEdge(node1, no2ne2));
				
				//If new total is less or equal then update edges otherwise quit the iteration
				if (newWeight <= sumOf4Edges) {//Remove old edges
											  tour.removeEdge(tour.getEdge(node1, no1ne1));
											  tour.removeEdge(tour.getEdge(node1, no1ne2));
											  tour.removeEdge(tour.getEdge(node2, no2ne1));
											  tour.removeEdge(tour.getEdge(node2, no2ne2));
											  
											  //Add new edges
											  DefaultWeightedEdge e1 = tour.addEdge(node2, no1ne1);
											  tour.setEdgeWeight(e1, graph.getEdgeWeight(graph.getEdge(node2, no1ne1))); 
											  
											  DefaultWeightedEdge e2 = tour.addEdge(node2, no1ne2);
											  tour.setEdgeWeight(e2, graph.getEdgeWeight(graph.getEdge(node2, no1ne2)));
											  
											  DefaultWeightedEdge e3 = tour.addEdge(node1, no2ne1);
											  tour.setEdgeWeight(e3, graph.getEdgeWeight(graph.getEdge(node1, no2ne1)));
											  
											  DefaultWeightedEdge e4 = tour.addEdge(node1, no2ne2);
											  tour.setEdgeWeight(e4, graph.getEdgeWeight(graph.getEdge(node1, no2ne2)));
				
											  //Update answer
											  min_dist = (min_dist - sumOf4Edges + newWeight);
											  System.out.println(min_dist);
				} else {}
		}
				
		return min_dist;
	}		
	
	
	static void createTour(SimpleWeightedGraph<Node, DefaultWeightedEdge> graph) {
		//Create a new graph to hold the TS tour.
		tour = new SimpleWeightedGraph<Node, DefaultWeightedEdge>(DefaultWeightedEdge.class);
		
		//Initialise min_time.
		min_dist = 0.0;
		
		//Get any node and set it as the first node.
		Iterator<Node> iter = graph.vertexSet().iterator();
		Node first_node = iter.next();
		
		//Also set it as the 'previous' node, for the vertex iteration to work.
		Node prev_node = first_node;
		
		//Add it as a vertex in the tour graph.
		tour.addVertex(first_node);
		
		//Iterate through the remaining vertices.
		while (iter.hasNext()) {
			//Get a node.
			Node node = iter.next();
			//Add it as a vertex in the tour graph.
			tour.addVertex(node);
			//Add and edge between it and the previous node.
			tour.addEdge(node, prev_node);
			DefaultWeightedEdge edge = graph.getEdge(node, prev_node);
			double weight = graph.getEdgeWeight(edge); 
			tour.setEdgeWeight(tour.getEdge(node, prev_node), weight);
			//Add the weight to min_dist;
			min_dist += weight;
			//Update the pointer 'previous node' to hold the current node.
			prev_node = node;
		}
		//Add an edge between the last and first nodes.
		tour.addEdge(first_node, prev_node);
		DefaultWeightedEdge edge = graph.getEdge(first_node, prev_node);
		double weight = graph.getEdgeWeight(edge);
		tour.setEdgeWeight(tour.getEdge(first_node, prev_node), weight);
		//Add the weight to min_dist;
		min_dist += weight;
		
		
	}

}
